#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,q,fa[N],cnt,a[N],b[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void join(int x,int y){
	fa[find(x)]=find(y);
}
map<int,int> mp,gg;
signed main() {
	freopen("destory.in","r",stdin);
	freopen("destory.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		join(u,v);
	}
	for(int i=1;i<=n;i++){
		int fd=find(i);
		if(!b[fd]) b[fd]=++cnt;
		a[i]=b[fd];
	}
	while(q--){
		int l,r;cin>>l>>r;mp.clear();gg.clear();
		for(int i=l;i<=r;i++) mp[a[i]]=1;
		int siz=mp.size(),L=l-1,tlh=0,ans=1e9;
		for(int i=l;i<=r;i++){
			while(1){
				if(L==r||tlh==siz) break;
				if(!gg[a[L+1]]) ++tlh;
				++gg[a[L+1]];
				++L;
			}
			if(tlh==siz) ans=min(ans,L-i+1);
			--gg[a[i]];if(!gg[a[i]]) --tlh;
		}
		cout<<ans<<'\n';
	}
	return 0;
}
